package 剑指offer;

/**
 * 
 * @author 兰伟朋
 *@time 2020年12月10日下午9:37:26
 *@see在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，
 *每一列都按照从上到下递增的顺序排序。
 *请完成一个高效的函数，输入这样的一个二维数组和一个整数，
 *判断数组中是否含有该整数。
 *
 */
public class _04二维数组中的查找 {
	/**
	 * 
	 *@time 2020年12月10日下午9:42:30
	 * 
	 *@param matrix
	 *@param target
	 *@return boolean
	 *
	 *@see暴力求解
	 */
	 public boolean findNumberIn2DArray1(int[][] matrix, int target) {
		 if(matrix==null||matrix.length==0||matrix[0].length==0)
			 return false;
		 int rows = matrix.length, columns = matrix[0].length;
		 for(int i=0;i<rows;i++)
			 for(int j=0;j<columns;j++) {
				 if(matrix[i][j]==target)
					 return true;
			 }
				 
		return false;
	    }
	 /**
	  * 
	  *@time 2020年12月10日下午9:49:14
	  * 
	  *@param matrix
	  *@param target
	  *@return boolean
	  *
	  *@see 形似二叉数，左边的元素大，右边的小，二叉搜索
	  */
	 public boolean findNumberIn2DArray2(int[][] matrix, int target) {
		  if(matrix==null||matrix.length==0||matrix[0].length==0)
              return false;
		 int i=matrix.length-1,j=0,colums=matrix[0].length;
		 while(i>=0&&j<colums) {
			 if(matrix[i][j]>target) i--;
			 else if(matrix[i][j]<target)j++;
			 else return true;
		 }
		return false;
		 
	 }
}
